package top.fengleifeng.question;

import top.fengleifeng.util.Constants;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年12月16日 4:17 下午
 */
public class Z部分排序 {

    //0-i    i-j   j-n   这种形式

    /**
     * 如果
     */
    class Solution {

        public int[] subSort(int[] array) {
            int[] result = new int[2];
            if (array.length <= 0) {
                result[0] = -1;
                result[1] = -1;
                return result;
            }
            int[][] dps = new int[array.length][4];
            dps[0][0] = array[0];
            dps[0][1] = array[0];
            dps[0][2] = -1;
            dps[0][3] = -1;
            for (int i = 1; i < array.length; i++) {
                if (array[i] >= dps[i - 1][1]) {
                    dps[i][0] = dps[i - 1][0];
                    dps[i][1] = array[i];
                    dps[i][2] = dps[i - 1][2];
                    dps[i][3] = dps[i - 1][3];
                } else {
                    dps[i][0] = Math.min(dps[i - 1][0], array[i]);
                    dps[i][1] = dps[i - 1][1];
                    //获取最小的数字
                    int preNow = dps[i - 1][2] == -1 ? Integer.MAX_VALUE : dps[i - 1][2];
                    dps[i][2] = Math.min(getStartIndex(array, i, array[i]), preNow);
                    dps[i][3] = i;
                }

            }

            result[0] = dps[array.length - 1][2];
            result[1] = dps[array.length - 1][3];
            return result;
        }

        private int getStartIndex(int[] array, int endIndex, int num) {
            for (int i = 0; i < endIndex; i++) {
                if (array[i] > num) {
                    return i;
                }
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19};
        int[] ints = new Z部分排序().new Solution().subSort(array);
        Constants.printArr(ints);
    }
}
